¿Cómo describimos matemáticamente los hilos invisibles que conectan a la sociedad? Ya sea el Números de Bacon que vinculan a Bela Lugosi con íconos de Hollywood o Grafos de Similitud que agrupan puntos de datos según su proximidad, Teoría de Grafos proporciona el lenguaje formal $G = (V, E)$ para modelar estos universos discretos.
1. La Anatomía de los Grafos
En esencia, un grafo consta de un conjunto de vértices ($V$) y un conjunto de aristas ($E$). Sin embargo, las reglas de interacción varían según la estructura:
- Grafo Simple: La forma más elegante; prohíbe bucles (aristas que conectan un vértice consigo mismo) y aristas paralelas (aristas redundantes entre los mismos dos puntos).
- Multigrafo: Permite bucles y aristas paralelas, comúnmente usado para modelar múltiples tipos de interacciones (por ejemplo, texto frente a llamada) entre los mismos dos nodos.
- Vértice Aislado: Un vértice $v$ es aislado si no hay ninguna arista incidente sobre él, representando un objeto sin relaciones en el conjunto actual.
En ciencia de datos, a menudo utilizamos una Función de Disimilitud para construir grafos:
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
Dibujamos una arista entre $v$ y $w$ solo si $s(v, w)$ cae por debajo de un umbral específico, construyendo así efectivamente una red de "vecinos".
2. Caminos, Conectividad y Componentes
Un camino es una secuencia de vértices y aristas. Si un camino visita cada vértice a lo sumo una vez, se denomina camino simple. La conectividad es el latido del grafo:
- Grafo Conectado: Existe un camino entre cada par de vértices en el grafo.
- Componentes: Si un grafo no está conectado, se divide en piezas disjuntas llamadas componentes. Cada componente es un subgrafo conexo maximal.
3. Subgrafos: La Arquitectura de Subconjuntos
Un subgrafo $G' = (V', E')$ es un subconjunto de un grafo $G$ tal que cada vértice en $V'$ existe en $V$, y cada arista en $E'$ conecta vértices encontrados en $V'$. Identificar subgrafos es fundamental para detectar patrones locales dentro de redes globales.